/**
 * 399. 除法求值
 * https://leetcode-cn.com/problems/evaluate-division/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {Map} relations
 * @param {string} a
 * @param {string} b
 * @param {Set} searched
 * @return {number}
 */
function searchRelation(relations, a, b, searched) {
  if (!relations.has(a) || !relations.has(b)) {
    return -1;
  }
  if (a === b) {
    return 1;
  }
  const relation = relations.get(a);
  const { childrenMap, children } = relation;
  if (childrenMap.has(b)) {
    return children[childrenMap.get(b)].value;
  }
  searched.add(a);
  for (let i = 0; i < children.length; i += 1) {
    if (searched.has(children[i].relation)) {
      continue;
    }
    const childValue = searchRelation(relations, children[i].relation, b, searched);
    if (childValue !== -1) {
      childrenMap.set(b, children.length);
      const value = children[i].value * childValue;
      children.push({
        relation: b,
        value,
      });
      return value;
    }
  }
  return -1;
}

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
function calcEquation(equations, values, queries) {
  const relations = new Map();
  for (let i = 0; i < equations.length; i += 1) {
    const [a, b] = equations[i];
    let relation = relations.get(a);
    if (!relation) {
      relation = {
        children: [],
        childrenMap: new Map(),
      };
      relations.set(a, relation);
    }
    relation.childrenMap.set(b, relation.children.length);
    relation.children.push({
      relation: b,
      value: values[i],
    });

    relation = relations.get(b);
    if (!relation) {
      relation = {
        children: [],
        childrenMap: new Map(),
      };
      relations.set(b, relation);
    }
    relation.childrenMap.set(a, relation.children.length);
    relation.children.push({
      relation: a,
      value: 1 / values[i],
    });
  }
  const result = new Array(queries.length).fill(0);
  for (let i = 0; i < queries.length; i += 1) {
    const [a, b] = queries[i];
    result[i] = searchRelation(relations, a, b, new Set());
  }
  return result;
}

console.log(displayBaseArray(calcEquation(
  [['a', 'b'], ['b', 'c']],
  [2.0, 3.0],
  [['a', 'c'], ['b', 'a'], ['a', 'e'], ['a', 'a'], ['x', 'x']],
)) === '[6,0.5,-1,1,-1]');
console.log(displayBaseArray(calcEquation(
  [['a', 'b'], ['b', 'c'], ['bc', 'cd']],
  [1.5, 2.5, 5.0],
  [['a', 'c'], ['c', 'b'], ['bc', 'cd'], ['cd', 'bc']],
)) === '[3.75,0.4,5,0.2]');
console.log(displayBaseArray(calcEquation(
  [['a', 'b']],
  [0.5],
  [['a', 'b'], ['b', 'a'], ['a', 'c'], ['x', 'y']],
)) === '[0.5,2,-1,-1]');
console.log(displayBaseArray(calcEquation(
  [['x1', 'x2'], ['x2', 'x3'], ['x3', 'x4'], ['x4', 'x5']],
  [3.0, 4.0, 5.0, 6.0],
  [['x1', 'x5'], ['x5', 'x2'], ['x2', 'x4'], ['x2', 'x2'], ['x2', 'x9'], ['x9', 'x9']],
)) === '[360,0.008333333333333333,20,1,-1,-1]');
console.log(displayBaseArray(calcEquation(
  [['x1', 'x2'], ['x2', 'x3'], ['x1', 'x4'], ['x2', 'x5']],
  [3.0, 0.5, 3.4, 5.6],
  [['x2', 'x4'], ['x1', 'x5'], ['x1', 'x3'], ['x5', 'x5'], ['x5', 'x1'], ['x3', 'x4'], ['x4', 'x3'], ['x6', 'x6'], ['x0', 'x0']],
)) === '[1.1333333333333333,16.799999999999997,1.5,1,0.05952380952380952,2.2666666666666666,0.4411764705882353,-1,-1]');
